// 小偷发现了一个新的可行窃的地区。
// 这个地区只有一个入口，我们称之为“根”。
// 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
// 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
// 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
// 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

function rob(root: TreeNode | null): number {
  if (!root) {
    // 递归出口
    return 0;
  }
  let money: number = root.val;
  if (root.left) {
    // 计算左孙节点合
    money += rob(root.left.right) + rob(root.left.left);
  }
  if (root.right) {
    // 计算右孙节点合
    money += rob(root.right.left) + rob(root.right.right);
  }
  //返回结果，比较祖孙和与儿子和哪个的钱数更多
  return Math.max(money, rob(root.left) + rob(root.right));
}

// 首先最直白的采用深度优先遍历的递归解法
// 回到最原始的情况思考，假设存在1个祖节点，祖节点存在2个父节点，每个父节点存在2个子节点
// 即形成了 1->2->4 的层级关系，不能偷相邻的节点，即意味着实质上是在比较
// 偷盗的祖节点+孙节点的金额与父节点的金额进行比较，多的那一个就是钱数更多的选择
// 根据上述的这个关系我们就可以设计出一个递归的算法（采用哈希表可以进行记忆化搜索的优化）。


// DP类声明
class DP {
  stole: number;
  unstole: number;
  constructor() {
    this.stole = 0;
    this.unstole = 0;
  }
}
// 暴露接口
function rob2(root: TreeNode | null): number {
  let resDP: DP = __calDp(root);
  return Math.max(resDP.stole, resDP.unstole);// 返回根节点DP偷与不偷情况中钱数最多的那种情况
}
function __calDp(root: TreeNode | null): DP {
  if (!root) {// 递归出口 返回底层DP变量
    return new DP();
  }
  let currDp: DP = new DP();// 声明当前的DP变量
  // 计算左右子树的DP变量
  let leftDp: DP = __calDp(root.left);
  let rightDp: DP = __calDp(root.right);
  currDp.stole = leftDp.unstole + rightDp.unstole + root.val;// 偷当前节点的状态转移方程
  currDp.unstole =// 不偷当前节点的状态转移方程
    Math.max(leftDp.stole, leftDp.unstole) +
    Math.max(rightDp.stole, rightDp.unstole);
  return currDp;
}

// 通过普通递归方式的求解，我们其实已经可以大致的推导出这道题目的状态转移方程了
// 在这道题目上我们可以实现树形的动态规划算法
// 从动态规划的角度来进行思考，我们先尝试去定义一个状态
// 对于任意一个节点，它存在两种状态，小偷去偷或者不去偷
// 1、若当前节点被偷，则当前节点的子节点都不能被偷
// 2、若当前节点不被偷，那么要求经过这两个子节点的方式需要拿到最多的钱数（但当前节点被不被偷无所谓）
// 我们定义一个DP对象，它存储两种代表当前节点的状态，即被偷或者不被偷时所能获得的最大钱数
// 接下来定义状态转移方程：
// 1、当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
// 2、当前节点选择偷：
// 当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
// 之后我们需要定义一个辅助函数来帮助我们用递归的方式计算自底向上计算DP变量
// 最后返回根节点的DP变量即可




